#!usr/bin/env python  
# -*- coding:utf-8 -*-
""" 
@author:robot
@file: find_max_coins.py 
@version:
@time: 2024/01/24

双循环不可避免

每个点执行什么操作，i和j需要在合理范围，当前位置点为0不可访问，返回0即可

访问输入位置点，需要考虑下一步向上下左右4个方位中的哪个方位走才能获得最多金币，
因此需要对四个方向进行遍历，遍历到每个方位时在递归调用函数，从而得到能获得的最多金币数，
与当前位置的金币数相加，即为从当前位置出发所能获得的最多金币数，返回即可。


需要特别注意的是，在处理当前节点时，由于需要遍历该节点上下左右4个方位，在计算当前节点4个方位的最大金币数时，为了避免重复访问到当前节点。
应该在遍历4个方位之前，将此节点的金币数置0，遍历完4个方位后再恢复当前节点值即可。
"""

directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]


def find_max_coins(grid):
    re = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] != 0:
                re = max(re, dfs(i, j, grid))
    return re


def dfs(i, j, grid):
    if len(grid) <= i or i < 0 or len(grid[0]) <= j or j < 0 or grid[i][j] == 0:
        return 0
    current_value = grid[i][j]
    grid[i][j] = 0
    max_ = 0
    for direct in directions:
        max_ = max(max_, dfs(i + direct[0], j + direct[1], grid))
    grid[i][j] = current_value
    return max_ + current_value


Grid = [
    [0, 2, 0],
    [1, 4, 3],
    [0, 5, 0],
]
print(find_max_coins(Grid))
